{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Technician Routing and Scheduling Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note**:\n",
    " \n",
    "This notebook, originally created for opti201 optimization training, is almost identical to Gurobi's [`technician_routing_scheduling`](\n",
    "https://colab.research.google.com/github/Gurobi/modeling-examples/blob/master/technician_routing_scheduling/technician_routing_scheduling.ipynb).\n",
    "Since an additional post processing step was required to export the results into csv files, and also some slight modifications in the constraints and objective functions needed to be made, a slightly different file name is used to differentiate between the two.\n",
    " \n",
    "To stay true to the original notebook, the changes are only made were absolutely necessary."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective and Prerequisites\n",
    "\n",
    "Try this modeling example to discover how mathematical optimization can help telecommunications firms automate and improve their technician assignment, scheduling, and routing decisions in order to ensure the highest levels of customer satisfaction.\n",
    "\n",
    "This modeling example is at the intermediate level, where we assume that you know Python and are familiar with the Gurobi Python API. In addition, you have some knowledge about building mathematical optimization models. To fully understand the content of this notebook, you should be familiar with object-oriented-programming.\n",
    "\n",
    "**Download the Repository** <br /> \n",
    "You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). \n",
    "\n",
    "**Gurobi License** <br /> \n",
    "In order to run this Jupyter Notebook properly, you must have a Gurobi license. If you do not have one, you can request an [evaluation license](https://www.gurobi.com/downloads/request-an-evaluation-license/?utm_source=3PW&utm_medium=OT&utm_campaign=WW-MU-TRA-OR-O_LEA-PR_NO-Q3_FY20_WW_JPME_technician-routing-sche-problem_COM_EVAL_GITHUB_&utm_term=technician-routing-scheduling-problem&utm_content=C_JPM) as a *commercial user*, or download a [free license](https://www.gurobi.com/academia/academic-program-and-licenses/?utm_source=3PW&utm_medium=OT&utm_campaign=WW-MU-TRA-OR-O_LEA-PR_NO-Q3_FY20_WW_JPME_technician-routing-sch-problem_ACADEMIC_EVAL_GITHUB_&utm_term=technician-routing-scheduling-problem&utm_content=C_JPM) as an *academic user*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Motivation\n",
    "The Technician Routing and Scheduling (TRS) is a common problem faced by telecommunication firms, which must be able to provide services for a large number of customers. With its limited resources, these firms must try to deliver timely, affordable and reliable services to maximize customer satisfaction. The TRS problem involves assignment, scheduling, and routing of multi-skilled technicians to serve customers with unique priorities, service time windows, processing times, skills requirements, and geographical locations. \n",
    "In the current practice, these decisions are often being made by operators via heuristics, sometimes manually -and this method\n",
    "can not only be time-consuming, \n",
    "but may also deviate from optima significantly. \n",
    "Using mathematical optimization to solve the\n",
    "TRS problem  will\n",
    "enable \n",
    "telecom operators and dispatchers to automate and improve their assignment, scheduling, and routing decisions, while achieving high customer satisfaction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "A telecom firm operates multiple service centers to serve its customers. \n",
    "Each service center has \n",
    "its technicians who are dispatched from the service center to work on their assigned jobs, and return to the center after all the jobs are completed. \n",
    "A technician has multiple skills and available working capacity that cannot be exceeded during the scheduling horizon. \n",
    "A service order/job has \n",
    "a known processing time, \n",
    "a customer-specified time window for starting the service, \n",
    "a deadline of completing the service, \n",
    "and its skill requirements. \n",
    "Depending on the nature of the job (routine maintenance or emergency), and relationship with the customer (existing, new), the firm assesses the importance of the job and assigns a priority score to it. \n",
    "A job is assigned to at most one technician who possesses the required \n",
    "skills, \n",
    "but the technician's available capacity during the scheduling horizon cannot be exceeded.\n",
    "To solve the  TRS problem, telecommunications companies must be able to\n",
    "simultaneously make three types of decisions: (i) the assignment of jobs to a technician at all the service centers; \n",
    "(ii) the routing of each technician, i.e. the sequence/order of customers for a technician to visit; \n",
    "(iii) and the earliest and latest scheduling of jobs, i.e. the earliest and latest time for a technician to arrive at a customer location and complete the corresponding job. \n",
    "The firm’s goal is to maximize the number of jobs completed.\n",
    "\n",
    "The following constraints must be satisfied:\n",
    "* A technician, if utilized, departs from the service center where he/she is based and returns to the same service center after his/her assigned jobs are completed.\n",
    "* A technician’s available capacity during the scheduling horizon cannot be exceeded.\n",
    "* A job, if selected, is assigned to at most one technician who  possesses the required skills.\n",
    "* A technician must arrive at a customer location during an interval (time window) specified by the customer, and must complete a job before the deadline required by the customer. This is an important constraint for guaranteeing customer satisfaction. \n",
    "\n",
    "The above basic TRS is a variant of the multi-depot vehicle routing problem with time windows, known as the MDVRPTW in the literature [1]. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution Approach\n",
    "\n",
    "Mathematical programming is a declarative approach where the modeler formulates a mathematical optimization model that captures the key aspects of a complex decision problem. The Gurobi Optimizer solves such models using state-of-the-art mathematics and computer science.\n",
    "\n",
    "A mathematical optimization model has five components, namely:\n",
    "\n",
    "* Sets and indices.\n",
    "* Parameters.\n",
    "* Decision variables.\n",
    "* Objective function(s).\n",
    "* Constraints.\n",
    "\n",
    "To simplify the MIP formulation, we consider that for each job's skill requirements, we can determine the subset of technicians that are qualified to perform the job based on the skills that the technicians have.\n",
    "\n",
    "We now present a MIP formulation for the basic TRS problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Formulation\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sets and Indices\n",
    "$j \\in J = \\{1,2,...,n\\}$: Index and set of jobs.\n",
    "\n",
    "$k \\in K$: Index and set of technicians.\n",
    "\n",
    "$K(j) \\subset K$: Subset of technicians qualified to perform job $j \\in J$ \n",
    "\n",
    "$d \\in D = \\{n+1, n+2, ...,n+m \\}$: Index and set of depots (service centers), where $m$ is the number of depots.\n",
    "\n",
    "$l, i, j \\in L = J \\cup D = \\{1,2,..., n+m \\}$: index and set of locations to visit.\n",
    "\n",
    "### Parameters\n",
    "$\\beta_{k,d} \\in \\{0,1\\}$: This parameter is equal 1 if technician $k \\in K$ must depart from and return to depot \n",
    "$d \\in D$; and 0 otherwise.\n",
    "\n",
    "$p_{j} \\in \\mathbb{R^{+}}$; Processing time (duration) of job $j \\in J$.\n",
    "\n",
    "$\\tau_{i,j} \\in \\mathbb{R^{+}}$: Travel time, in minutes, from location $i \\in L$ to location $j \\in L$.\n",
    "\n",
    "$W_{k} \\in \\mathbb{N}$: Workload limit of technician $k \\in K$ during the planning horizon. That is, the number of hours, in minutes, that the technician is available for the next work day.\n",
    "\n",
    "$\\pi_{j} \\in \\{1,2,3,4\\}$: Priority weight of job $j \\in J$, a larger number means higher priority.\n",
    "\n",
    "$a_{j} \\in \\mathbb{R^{+}} $: Earliest time to start the service at location of job $j \\in J$.\n",
    "\n",
    "$b_{j} \\in \\mathbb{R^{+}} $: Latest time to start the service at location of job $j \\in J$.\n",
    "\n",
    "$M \\in \\mathbb{N}$: This is a very large number. This number is determined as follows: the planning horizon is 10 working hours (i.e. 600 min). We want the value of $M$ to be an order of magnitude larger than the planning horizon. Therefore, we set M = 6100.\n",
    "\n",
    "### Decision Variables\n",
    "\n",
    "$x_{j,k} \\in \\{0,1\\}$: This variable is equal 1 if job $j \\in J$ is assigned to technician $k \\in K$, and 0 otherwise.\n",
    "\n",
    "$u_{k} \\in \\{0,1\\}$: This variable is equal 1 if technician $k \\in K$  is used to perform a job, and 0 otherwise.\n",
    "\n",
    "$y_{i,j,k} \\in \\{0,1\\}$: This variable is equal 1 if technician $k \\in K$  travels from location $i \\in L$ to location \n",
    "$j \\in L$; and 0 otherwise.\n",
    "\n",
    "$t_{j} \\geq 0$: This variable determines the time to arrive or start the service at location $j \\in J$.\n",
    "\n",
    "$g_{j}$: This variable is equal 1 if job $j \\in J$ cannot be filled, and 0 otherwise. \n",
    "\n",
    "### Objective Function\n",
    "\n",
    "- **Minimize Unfilled Jobs:** The Objective function is to minimize the number of jobs that could not be completed on time. We're also interested to get the earliest arrival time at each location. So, we minimize the time of arrival at each location as well.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in J} \\pi_{j} \\cdot M \\cdot g_{j} + \\sum_{j \\in J} 0.01 \\cdot M \\cdot t_{j}\n",
    "\\tag{0}\n",
    "\\end{equation}\n",
    "\n",
    "**Note**: We want to treat the constraints about starting the jobs within a time window as hard constraints. Hard constraints can not be violated. We treat the constraints of filling the jobs demand as soft constraints. Soft constraints can be violated, but the violation will incur in a huge penalty. We assume that not filling jobs demand greatly deteriorate customer satisfaction, consequently should incur large penalties. Recall that the value of the parameter $M$ is a large number, then the penalty associated with not filling a job is determined as follows: $\\pi_{j} \\cdot M$.\n",
    "\n",
    "To get the earliest arrival times of technicians at customer locations, we also add a term $0.01 \\cdot M \\cdot t_{j}$.\n",
    "\n",
    "\n",
    "### Constraints\n",
    "\n",
    "- **Assign qualified technicians:** For each job, we  assign one technician who is qualified for the job, or a gap is declared. \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{k \\in K(j)} x_{j,k} + g_{j} = 1 \\quad \\forall j \\in J\n",
    "\\tag{1}\n",
    "\\end{equation}\n",
    "\n",
    "**Note**: The penalty of the gap variable $g_{j}$ is ($\\pi_{j} \\cdot M$) which is a large number to discourage \n",
    "not being able to satisfy demand.\n",
    "\n",
    "- **Only one technician:** For each job, we only allow one technician to be assigned.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{k \\in K} x_{j,k} \\leq 1 \\quad \\forall j \\in J\n",
    "\\tag{2}\n",
    "\\end{equation}\n",
    "\n",
    "- **Technician capacity:** For each technician, we ensure that the available capacity of the technician is not exceeded. \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in J}  p_{j} \\cdot x_{j,k} + \\sum_{i \\in L} \\sum_{j \\in L} \\tau_{i,j} \\cdot y_{i,j,k} \\leq W_{k} \\cdot u_{k} \\quad \\forall k \\in K\n",
    "\\tag{3}\n",
    "\\end{equation}\n",
    "\n",
    "- **Technician tour:** For each technician and job, we ensure that if the technician is assigned to the job, then the technician must travel to another location (to form a tour). \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in L}  y_{i,j,k} = x_{i,k} \\quad \\forall i \\in J, k \\in K\n",
    "\\tag{4}\n",
    "\\end{equation}\n",
    "\n",
    "- For each technician and job, we ensure that if a technician is assigned to the job, then the technician must travel from another location to the location of the job (to form a tour). \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{i \\in L}  y_{i,j,k} = x_{j,k} \\quad \\forall j \\in J, k \\in K\n",
    "\\tag{5}\n",
    "\\end{equation}\n",
    "\n",
    "- **Same depot:** For each technician and depot, we ensure that a technician, if assigned to any job, must depart from and return to the service center (depot) where the technician is based. \n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{j \\in J}  y_{d,j,k} = \\beta_{k,d} \\cdot u_{k} \\quad \\forall  k \\in K, d \\in D\n",
    "\\tag{6}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{i \\in J}  y_{i,d,k} = \\beta_{k,d} \\cdot u_{k} \\quad \\forall  k \\in K, d \\in D\n",
    "\\tag{7}\n",
    "\\end{equation}\n",
    "\n",
    "- **Temporal relationship:** For each location and job, we ensure the temporal relationship between two consecutive jobs served by the same technician. That is, if a technician $k$ travels from job $i$ to job $j$, then the start of the service time at job $j$ must be no less than the completion time of job $i$ plus the travel time from job $i$ to job $j$. \n",
    "\n",
    "\\begin{equation}\n",
    "t_{j} \\geq t_{i} + p_{i} + \\tau_{i,j} - M \\cdot (1 - \\sum_{k \\in K}  y_{i,j,k}) \\quad \\forall i \\in L, j \\in J\n",
    "\\tag{8}\n",
    "\\end{equation}\n",
    "\n",
    "**Note**: Observe that if the technician $k$ travels from the location of job $i$ to the location of job $j$, then\n",
    "$\\sum_{k \\in K}  y_{i,j,k} = 1$. Therefore, $M \\cdot (1 - \\sum_{k \\in K}  y_{i,j,k}) = 0$, and the constraint \n",
    "$t_{j} \\geq t_{i} + p_{i} + \\tau_{i,j}$ would be properly enforced. Now consider the case where the technician $k$ does not travel  from the location of job $i$ to the location of job $j$. Hence, $\\sum_{k \\in K}  y_{i,j,k} = 0$ and \n",
    "$M \\cdot (1 - \\sum_{k \\in K}  y_{i,j,k}) = M$. In this case, this constraint becomes \n",
    "$t_{j} \\geq t_{i} + p_{i} + \\tau_{i,j} - M$. But $M$ is a very large number, then $t_{i} + p_{i} + \\tau_{i,j} - M < 0$ and \n",
    "since $t_{j} \\geq 0$, this constraint is redundant.\n",
    "\n",
    "- **Time window:** For each job $j \\in J$ ensure that the time window for the job is satisfied.\n",
    "\n",
    "\\begin{equation}\n",
    "t_{j} \\geq a_{j} \\quad \\forall j \\in J\n",
    "\\tag{9}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "t_{j} \\leq b_{j} \\quad \\forall j \\in J\n",
    "\\tag{10}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Instance\n",
    "\n",
    "In this scenario, we consider the problem of routing and scheduling technicians for the next work-day in such a way that the delay of customer appointments is minimized. The telecom firm has seven technicians: Albert, Bob, Carlos, Doris, Ed, Flor, and Gina. There are two service centers: Heidelberg and Freiburg im Breisgau. Technicians are based at only one of these service centers. The number of hours available and the service center base (depot) for each technician is described in the following table.\n",
    "\n",
    "| <i></i> | Albert | Bob | Carlos | Doris | Ed | Flor | Gina |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- |\n",
    "| Minutes | 480 | 480 | 480 | 480 | 480 | 360 | 360 |\n",
    "| Depot | Heidelberg | Heidelberg | Freiburg im Breisgau | Freiburg im Breisgau | Heidelberg | Freiburg im Breisgau | Heidelberg |\n",
    "\n",
    "The telecom company has different type of jobs. \n",
    "The following table shows the priority (4 for the highest priority and 1 for the least important) and duration (in hours) of a job type.\n",
    "\n",
    "| <i></i> | Priority | Duration (min) |\n",
    "| --- | --- | --- | \n",
    "| Equipment Installation | 2 | 60 |\n",
    "| Equipment Setup | 3 | 30 |\n",
    "| Inspect/Service Equipment | 1 | 60 |\n",
    "| Repair - Regular | 1 | 60 |\n",
    "| Repair - Important | 2 | 120 |\n",
    "| Repair - Urgent | 3 | 90 |\n",
    "| Repair - Critical | 4 | 60 |\n",
    "\n",
    "The following table shows the jobs that each technician is qualified for.\n",
    "\n",
    "| <i></i> | Albert | Bob | Carlos | Doris | Ed | Flor | Gina |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- |\n",
    "| Equipment Installation | - | - | - | 1 | - | 1 | 1 |\n",
    "| Equipment Setup | 1 | 1 | 1 | 1 | - | - | 1 |\n",
    "| Inspect/Service Equipment | 1 | - | 1 | - | 1 | - | - |\n",
    "| Repair - Regular | - | 1 | 1 | - | 1 | 1 | 1 |\n",
    "| Repair - Important | - | - | - | 1 | - | 1 | 1 |\n",
    "| Repair - Urgent | - | 1 | 1 | - | 1 | 1 | 1 |\n",
    "| Repair - Critical | - | - | - | 1 | - | - | 1 |\n",
    "\n",
    "The telecom company receives customers' requests for a specific job type, appointment (due) time, and the service time window where the technician can arrive. The following table shows the customers' orders and their requirements. For each customer, the location is specified.\n",
    "\n",
    "| <i></i> | C1:Mannheim  | C2: Karlsruhe  | C3: Baden-Baden  | C4: Bühl  | C5: Offenburg | C6: Lahr/Schwarzwald | C7: Lörrach |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- |\n",
    "| Job type | Equipment Setup | Equipment Setup | Repair - Regular | Equipment Installation | Equipment Installation | Repair - Critical | Inspect/Service Equipment |\n",
    "| Due time | 8:00 | 10:00 | 11:00  | 12:00 | 14:00 | 15:00 | 16:00 |\n",
    "| Time Window | 7:00-7:30 | 7:30-9:30 | 8:00-10:00 | 9:00-11:00 | 11:00-13:00 | 12:00-14:00 | 13:00-15:00 |\n",
    "\n",
    "The planning horizon is from 7:00 to 17:00, or 10 hours. The time period is in minutes, then the due time and time windows will be translated into minutes starting at 0 minutes and ending at 600 minutes. For example, for customer C2 the due time is at 10:00  (180 min), and the time window is from 7:30 to 9:30  (30 min to  150 min). \n",
    "\n",
    "The following table shows the travel time (in minutes) from any depot or customer location to any depot or customer location.\n",
    "\n",
    "| <i></i> | Heidelberg | Freiburg im Breisgau | Mannheim  | Karlsruhe  | Baden-Baden  | Bühl  | Offenburg | Lahr/Schwarzwald | Lörrach |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- |--- |--- |\n",
    "| Heidelberg | - | 120 | 24 | 50 | 67 | 71 | 88 | 98 | 150 |\n",
    "| Freiburg im Breisgau | - | - | 125 | 85 | 68 | 62 | 45 | 39 | 48 |\n",
    "| Mannheim | - | - | - | 53 | 74 | 77 | 95 | 106 | 160 |\n",
    "| Karlsruhe | - | - | - | - | 31 | 35 | 51 | 61 | 115 |\n",
    "| Baden-Baden | - | - | - | - | - | 16 | 36 | 46 | 98 |\n",
    "| Bühl | - | - | - | - | - | - | 30 | 40 | 92 |\n",
    "| Offenburg | - | - | - | - | - | - | - | 26 | 80 |\n",
    "| Lahr/Schwarzwald | - | - | - | - | - | - | - | - | 70 |\n",
    "| Lörrach | - | - | - | - | - | - | - | - | - |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Implementation\n",
    "\n",
    "In this Jupyter Notebook, we use the following libraries:\n",
    "\n",
    "* `sys` to access system-specific parameters and functions.\n",
    "* `pandas` to read data from Excel files.\n",
    "* `gurobipy` Gurobi Optimizer library.\n",
    "\n",
    "This implementation is based on object-oriented-programming.\n",
    "\n",
    "### Helper Classes\n",
    "\n",
    "The following classes properly organize the input data of the MIP model.\n",
    "\n",
    "* `Technician`.\n",
    "* `Job`.\n",
    "* `Customer`.\n",
    "\n",
    "### Helper Functions\n",
    "\n",
    "* `solve_trs0` builds and solves MIP model.\n",
    "* `get_latest_times` solves for latest arrival times at customer locations, given the solution from the MIP Model.\n",
    "* `printScen` prints headings for output reports.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy\n",
    "%pip install pandas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:02:34.619049Z",
     "start_time": "2023-11-06T20:02:34.199948Z"
    }
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "import pandas as pd\n",
    "\n",
    "# tested with Gurobi v10.0.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:02:35.761775Z",
     "start_time": "2023-11-06T20:02:35.745925Z"
    }
   },
   "outputs": [],
   "source": [
    "class Technician():\n",
    "    def __init__(self, name, cap, depot):\n",
    "        self.name = name\n",
    "        self.cap = cap\n",
    "        self.depot = depot\n",
    "\n",
    "    def __str__(self):\n",
    "        return f\"Technician: {self.name}\\n  Capacity: {self.cap}\\n  Depot: {self.depot}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:02:37.083045Z",
     "start_time": "2023-11-06T20:02:37.074852Z"
    }
   },
   "outputs": [],
   "source": [
    "class Job():\n",
    "    def __init__(self, name, priority, duration, coveredBy):\n",
    "        self.name = name\n",
    "        self.priority = priority\n",
    "        self.duration = duration\n",
    "        self.coveredBy = coveredBy\n",
    "\n",
    "    def __str__(self):\n",
    "        about = f\"Job: {self.name}\\n  Priority: {self.priority}\\n  Duration: {self.duration}\\n  Covered by: \"\n",
    "        about += \", \".join([t.name for t in self.coveredBy])\n",
    "        return about"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:02:39.474001Z",
     "start_time": "2023-11-06T20:02:39.464531Z"
    }
   },
   "outputs": [],
   "source": [
    "class Customer():\n",
    "    def __init__(self, name, loc, job, tStart, tEnd, tDue):\n",
    "        self.name = name\n",
    "        self.loc = loc\n",
    "        self.job = job\n",
    "        self.tStart = tStart\n",
    "        self.tEnd = tEnd\n",
    "        self.tDue = tDue\n",
    "\n",
    "    def __str__(self):\n",
    "        coveredBy = \", \".join([t.name for t in self.job.coveredBy])\n",
    "        return f\"Customer: {self.name}\\n  Location: {self.loc}\\n  Job: {self.job.name}\\n  Priority: {self.job.priority}\\n  Duration: {self.job.duration}\\n  Covered by: {coveredBy}\\n  Start time: {self.tStart}\\n  End time: {self.tEnd}\\n  Due time: {self.tDue}\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scenario\n",
    "\n",
    "For this scenario, there is enough technician capacity to fill all customers demand. To run the base scenario, consider the spreadsheet file `data-Sce0.xlsx` and insert this name when you open the Excel workbook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:02:42.314709Z",
     "start_time": "2023-11-06T20:02:41.730794Z"
    }
   },
   "outputs": [],
   "source": [
    "# Read Excel workbook\n",
    "excel_file = 'https://raw.githubusercontent.com/decision-spot/technician_assignment/main/data-Sce0.xlsx'\n",
    "df = pd.read_excel(excel_file, sheet_name='Technicians')\n",
    "df = df.rename(columns={df.columns[0]: \"name\", df.columns[1]: \"cap\", df.columns[2]: \"depot\"})\n",
    "\n",
    "df1 = df.drop(df.columns[3:], axis=1).drop(df.index[[0,1]])\n",
    "# Create Technician objects\n",
    "technicians = [Technician(*row) for row in df1.itertuples(index=False, name=None)]\n",
    "# print(df1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:02:44.006682Z",
     "start_time": "2023-11-06T20:02:43.992652Z"
    }
   },
   "outputs": [],
   "source": [
    "# Read job data\n",
    "jobs=[]\n",
    "for j in range(3, len(df.columns)):\n",
    "    coveredBy = [t for i, t in enumerate(technicians) if df.iloc[2+i,j]==1]\n",
    "    thisJob = Job(df.iloc[2:,j].name, df.iloc[0,j], df.iloc[1,j], coveredBy)\n",
    "    jobs.append(thisJob)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:02:46.602601Z",
     "start_time": "2023-11-06T20:02:46.426647Z"
    }
   },
   "outputs": [],
   "source": [
    "# Read location data\n",
    "df_locations = pd.read_excel(excel_file, sheet_name='Locations', index_col=0) #, skiprows=1, index_col=0)\n",
    "\n",
    "# Extract locations and initialize distance dictionary\n",
    "locations = df_locations.index\n",
    "dist = {(l, l): 0 for l in locations}\n",
    "\n",
    "# Populate distance dictionary\n",
    "for i, l1 in enumerate(locations):\n",
    "    for j, l2 in enumerate(locations):\n",
    "        if i < j:\n",
    "            dist[l1, l2] = df_locations.iloc[i, j]\n",
    "            dist[l2, l1] = dist[l1, l2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-06T20:02:51.920086Z",
     "start_time": "2023-11-06T20:02:51.490422Z"
    }
   },
   "outputs": [],
   "source": [
    "# Read customer data\n",
    "df_customers = pd.read_excel(excel_file, sheet_name='Customers')\n",
    "\n",
    "customers = []\n",
    "for i, c in enumerate(df_customers.iloc[:, 0]):\n",
    "    job_name = df_customers.iloc[i, 2]\n",
    "\n",
    "    # Find the corresponding Job object\n",
    "    matching_job = next((job for job in jobs if job.name == job_name), None)\n",
    "\n",
    "    if matching_job is not None:\n",
    "        # Create Customer object using corresponding Job object\n",
    "        this_customer = Customer(c, df_customers.iloc[i, 1], matching_job, *df_customers.iloc[i, 3:])\n",
    "        customers.append(this_customer)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To determine the latest times for a technician to arrive at a customer location and complete the job, you can calculate it by iterating over the sequence of customers to be served by the technician in reverse order.\n",
    "\n",
    "The latest time a technician can arrive at a customer location is constrained by two factors. First, it is upper-bounded by the customer-specified time window's End Time.  \n",
    "Second, it is also limited by the following: the latest arrival time at the next customer location in the sequence minus the job duration at the current customer location and the distance between the two customer locations. Additionally, it's essential for the technician to reach the depot location after completing all the assigned jobs by time t = 600."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-03T18:16:45.211980Z",
     "start_time": "2023-11-03T18:16:45.196283Z"
    }
   },
   "outputs": [],
   "source": [
    "def get_latest_times(customers, technician):\n",
    "    latest = dict()\n",
    "    d = dist[customers[-1].loc, technician.depot]   # distance back to the depot\n",
    "    prev_latest = min(customers[-1].tEnd, 600 - d - customers[-1].job.duration)\n",
    "    latest[customers[-1].loc] = prev_latest\n",
    "    for i in range(len(customers) - 2, -1, -1):\n",
    "        d = dist[customers[i].loc, customers[i + 1].loc]\n",
    "        latest_end = min(prev_latest - d - customers[i].job.duration, customers[i].tEnd)\n",
    "        latest[customers[i].loc] = latest_end\n",
    "        prev_latest = latest_end\n",
    "    return latest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We added another function `create_excel_output` inside the `solve_trs0` function to store the solution of the problem in two tables: **routes** and **orders**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-03T18:16:45.245086Z",
     "start_time": "2023-11-03T18:16:45.212896Z"
    }
   },
   "outputs": [],
   "source": [
    "def solve_trs0(technicians, customers, dist):\n",
    "    # Build useful data structures\n",
    "    K = [k.name for k in technicians]\n",
    "    C = [j.name for j in customers]\n",
    "    J = [j.loc for j in customers]\n",
    "    L = list(set([l[0] for l in dist.keys()]))\n",
    "    D = list(set([t.depot for t in technicians]))\n",
    "    cap = {k.name: k.cap for k in technicians}\n",
    "    loc = {j.name: j.loc for j in customers}\n",
    "    depot = {k.name: k.depot for k in technicians}\n",
    "    canCover = {j.name: [k.name for k in j.job.coveredBy] for j in customers}\n",
    "    dur = {j.name: j.job.duration for j in customers}\n",
    "    tStart = {j.name: j.tStart for j in customers}\n",
    "    tEnd = {j.name: j.tEnd for j in customers}\n",
    "    priority = {j.name: j.job.priority for j in customers}\n",
    "\n",
    "    ### Create model\n",
    "    m = gp.Model(\"trs0\")\n",
    "\n",
    "    ### Decision variables\n",
    "    # Customer-technician assignment\n",
    "    x = m.addVars(C, K, vtype=GRB.BINARY, name=\"x\")\n",
    "\n",
    "    # Technician assignment\n",
    "    u = m.addVars(K, vtype=GRB.BINARY, name=\"u\")\n",
    "\n",
    "    # Edge-route assignment to technician\n",
    "    y = m.addVars(L, L, K, vtype=GRB.BINARY, name=\"y\")\n",
    "\n",
    "    # Technician cannot leave or return to a depot that is not its base\n",
    "    for k in technicians:\n",
    "        for d in D:\n",
    "            if k.depot != d:\n",
    "                for i in L:\n",
    "                    y[i, d, k.name].ub = 0\n",
    "                    y[d, i, k.name].ub = 0\n",
    "\n",
    "    # Start time of service\n",
    "    t = m.addVars(L, ub=600, name=\"t\")\n",
    "\n",
    "    # Unfilled jobs\n",
    "    g = m.addVars(C, vtype=GRB.BINARY, name=\"g\")\n",
    "\n",
    "    ### Constraints\n",
    "\n",
    "    # A technician must be assigned to a job, or a gap is declared (1)\n",
    "    m.addConstrs((gp.quicksum(x[j, k] for k in canCover[j]) + g[j] == 1 for j in C), name=\"assignToJob\")\n",
    "\n",
    "    # At most one technician can be assigned to a job (2)\n",
    "    m.addConstrs((x.sum(j, '*') <= 1 for j in C), name=\"assignOne\")\n",
    "\n",
    "    # Technician capacity constraints (3)\n",
    "    capLHS = {k: gp.quicksum(dur[j] * x[j, k] for j in C) + \\\n",
    "                 gp.quicksum(dist[i, j] * y[i, j, k] for i in L for j in L) for k in K}\n",
    "    m.addConstrs((capLHS[k] <= cap[k] * u[k] for k in K), name=\"techCapacity\")\n",
    "\n",
    "    # Technician tour constraints (4 and 5)\n",
    "    m.addConstrs((y.sum('*', loc[j], k) == x[j, k] for k in K for j in C), \\\n",
    "                 name=\"techTour1\")\n",
    "    m.addConstrs((y.sum(loc[j], '*', k) == x[j, k] for k in K for j in C), \\\n",
    "                 name=\"techTour2\")\n",
    "\n",
    "    # Same depot constraints (6 and 7)\n",
    "    m.addConstrs((gp.quicksum(y[j, depot[k], k] for j in J) == u[k] for k in K), \\\n",
    "                 name=\"sameDepot1\")\n",
    "    m.addConstrs((gp.quicksum(y[depot[k], j, k] for j in J) == u[k] for k in K), \\\n",
    "                 name=\"sameDepot2\")\n",
    "\n",
    "    # Temporal constraints (8) for customer locations\n",
    "    M = {(i, j): 600 + dur[i] + dist[loc[i], loc[j]] for i in C for j in C}\n",
    "    m.addConstrs((t[loc[j]] >= t[loc[i]] + dur[i] + dist[loc[i], loc[j]] \\\n",
    "                  - M[i, j] * (1 - gp.quicksum(y[loc[i], loc[j], k] for k in K)) \\\n",
    "                  for i in C for j in C), name=\"tempoCustomer\")\n",
    "\n",
    "    # Temporal constraints (8) for depot locations\n",
    "    M = {(i, j): 600 + dist[i, loc[j]] for i in D for j in C}\n",
    "    m.addConstrs((t[loc[j]] >= t[i] + dist[i, loc[j]] \\\n",
    "                  - M[i, j] * (1 - y.sum(i, loc[j], '*')) for i in D for j in C), \\\n",
    "                 name=\"tempoDepot\")\n",
    "\n",
    "    # Time window constraints (9 and 10)\n",
    "    m.addConstrs((t[loc[j]] >= tStart[j] for j in C), name=\"timeWinA\")\n",
    "    m.addConstrs((t[loc[j]] <= tEnd[j] for j in C), name=\"timeWinB\")\n",
    "\n",
    "    ### Objective function\n",
    "    M = 6100\n",
    "\n",
    "    m.setObjective(gp.quicksum(M * priority[j] * g[j] for j in C) + gp.quicksum(0.01 * M * t[k] for k in L),\n",
    "                   GRB.MINIMIZE)\n",
    "\n",
    "    m.write(\"TRS0.lp\")\n",
    "    m.optimize()\n",
    "\n",
    "    status = m.Status\n",
    "    if status in [GRB.INF_OR_UNBD, GRB.INFEASIBLE, GRB.UNBOUNDED]:\n",
    "        print(\"Model is either infeasible or unbounded.\")\n",
    "        sys.exit(0)\n",
    "    elif status != GRB.OPTIMAL:\n",
    "        print(\"Optimization terminated with status {}\".format(status))\n",
    "        sys.exit(0)\n",
    "\n",
    "    ### Print results\n",
    "    # Assignments\n",
    "    print(\"\")\n",
    "    for j in customers:\n",
    "        if g[j.name].X > 0.5:\n",
    "            jobStr = \"Nobody assigned to {} ({}) in {}\".format(j.name,j.job.name,j.loc)\n",
    "        else:\n",
    "            for k in K:\n",
    "                if x[j.name, k].X > 0.5:\n",
    "                    jobStr = f\"{k} assigned to {j.name} ({j.job.name}) in {j.loc}. Start at t={t[j.loc].X:.2f}.\"\n",
    "        print(jobStr)\n",
    "\n",
    "    # Technicians\n",
    "    print(\"\")\n",
    "    for k in technicians:\n",
    "        if u[k.name].X > 0.5:\n",
    "            cur = k.depot\n",
    "            route = k.depot\n",
    "            while True:\n",
    "                for j in customers:\n",
    "                    if y[cur,j.loc,k.name].X > 0.5:\n",
    "                        route += (f\" -> {j.loc} (dist={dist[cur, j.loc]}, t={t[j.loc].X:.2f},\"\n",
    "                                  f\" proc={j.job.duration}, a={tStart[j.name]}, b={tEnd[j.name]})\")\n",
    "                        cur = j.loc\n",
    "                for i in D:\n",
    "                    if y[cur,i,k.name].X > 0.5:\n",
    "                        route += \" -> {} (dist={})\".format(i,dist[cur, i])\n",
    "                        cur = i\n",
    "                        break\n",
    "                if cur == k.depot:\n",
    "                    break\n",
    "            print(\"{}'s route: {}\".format(k.name, route))\n",
    "        else:\n",
    "            print(\"{} is not used\".format(k.name))\n",
    "\n",
    "            \n",
    "    # Utilization\n",
    "    print(\"\")\n",
    "    for k in K:\n",
    "        used = capLHS[k].getValue()\n",
    "        total = cap[k]\n",
    "        util = used / cap[k] if cap[k] > 0 else 0\n",
    "        print(\"{}'s utilization is {:.2%} ({:.2f}/{:.2f})\".format(k, util, used, cap[k]))\n",
    "    totUsed = sum(capLHS[k].getValue() for k in K)\n",
    "    totCap = sum(cap[k] for k in K)\n",
    "    totUtil = totUsed / totCap if totCap > 0 else 0\n",
    "    print(\"Total technician utilization is {:.2%} ({:.2f}/{:.2f})\".format(totUtil, totUsed, totCap))\n",
    "    \n",
    "    def create_excel_output():\n",
    "        routes_cols = ['Route ID', 'Technician Name', 'Origin Location', 'Total Travel Time', 'Total Processing Time',\n",
    "                       'Total Time', 'Earliest Start Time', 'Latest Start Time', 'Earliest End Time',\n",
    "                       'Latest End Time', 'Num Jobs']\n",
    "        routes_list = []\n",
    "        orders_cols = ['Route ID', 'Stop Number', 'Customer Name', 'Technician Name', 'Location Name', 'Job type',\n",
    "                       'Processing Time', 'Customer Time Window Start', 'Customer Time Window End',\n",
    "                       'Earliest Start', 'Latest Start', 'Earliest End', 'Latest End', ]\n",
    "        route_id = 0\n",
    "        orders_list = []\n",
    "        for k in technicians:\n",
    "            if u[k.name].X > 0.5:\n",
    "                customers_list = []\n",
    "                route_id += 1\n",
    "                total_distance, total_travel_time, total_processing_time = 0, 0, 0\n",
    "                cur = k.depot\n",
    "                while True:\n",
    "                    for j in customers:\n",
    "                        if y[cur, j.loc, k.name].X > 0.5:\n",
    "                            total_travel_time += dist[cur, j.loc]\n",
    "                            total_distance += dist[cur, j.loc]\n",
    "                            total_processing_time += j.job.duration\n",
    "                            customers_list.append(j)\n",
    "                            cur = j.loc\n",
    "                    for i in D:\n",
    "                        if y[cur, i, k.name].X > 0.5:\n",
    "                            total_travel_time += dist[cur, i]\n",
    "                            total_distance += dist[cur, i]\n",
    "                            cur = i\n",
    "                            break\n",
    "                    if cur == k.depot:\n",
    "                        break\n",
    "                latest = get_latest_times(customers_list, k)\n",
    "\n",
    "                # append customers to the list of orders\n",
    "                for i, j in enumerate(customers_list):\n",
    "                    orders_list.append([route_id, i + 1, j.name, k.name, j.loc, j.job.name,\n",
    "                                        j.job.duration, tStart[j.name], tEnd[j.name],\n",
    "                                        t[j.loc].X, latest[j.loc],\n",
    "                                        t[j.loc].X + j.job.duration, latest[j.loc] + j.job.duration])\n",
    "\n",
    "                # append route to routes list\n",
    "                earliest_start_route = t[customers_list[0].loc].X - dist[k.depot, customers_list[0].loc]\n",
    "                latest_start_route = latest[customers_list[0].loc] - dist[k.depot, customers_list[0].loc]\n",
    "                earliest_end_route = t[customers_list[-1].loc].X + customers_list[-1].job.duration + \\\n",
    "                                     dist[customers_list[-1].loc, k.depot]\n",
    "                latest_end_route = latest[customers_list[-1].loc] + customers_list[-1].job.duration + \\\n",
    "                                   dist[customers_list[-1].loc, k.depot]\n",
    "\n",
    "                routes_list.append([route_id, k.name, k.depot, total_travel_time, total_processing_time,\n",
    "                                    earliest_end_route - earliest_start_route, earliest_start_route,\n",
    "                                    latest_start_route, earliest_end_route, latest_end_route, len(customers_list)])\n",
    "        # Convert to dataframe and write to excel\n",
    "        routes_df = pd.DataFrame.from_records(routes_list, columns=routes_cols)\n",
    "        routes_df.to_csv('routes.csv', index=False)\n",
    "        orders_df = pd.DataFrame.from_records(orders_list, columns=orders_cols)\n",
    "        orders_df.to_csv('orders.csv', index=False)\n",
    "    \n",
    "    # create output files\n",
    "    create_excel_output()\n",
    "    \n",
    "    m.dispose()\n",
    "    gp.disposeDefaultEnv()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-03T18:16:45.260973Z",
     "start_time": "2023-11-03T18:16:45.245680Z"
    }
   },
   "outputs": [],
   "source": [
    "def printScen(scenStr):\n",
    "    sLen = len(scenStr)\n",
    "    print(\"\\n\" + \"*\"*sLen + \"\\n\" + scenStr + \"\\n\" + \"*\"*sLen + \"\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-03T18:16:45.396593Z",
     "start_time": "2023-11-03T18:16:45.262977Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "***************************\n",
      "Solving base scenario model\n",
      "***************************\n",
      "\n",
      "Set parameter Username\n",
      "Academic license - for non-commercial use only - expires 2024-09-19\n",
      "Warning: variable name \"y[Karlsruhe,Freiburg im Breisgau,Albert]\" has a space\n",
      "Warning: constraint name \"tempoDepot[Freiburg im Breisgau,Customer1]\" has a space\n",
      "Warning: to let Gurobi read it back, use rlp format\n",
      "Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)\n",
      "\n",
      "CPU model: 11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz, instruction set [SSE2|AVX|AVX2|AVX512]\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "\n",
      "Optimize a model with 210 rows, 639 columns and 2301 nonzeros\n",
      "Model fingerprint: 0x5263eee2\n",
      "Variable types: 9 continuous, 630 integer (630 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 8e+02]\n",
      "  Objective range  [6e+01, 2e+04]\n",
      "  Bounds range     [1e+00, 6e+02]\n",
      "  RHS range        [1e+00, 6e+02]\n",
      "Found heuristic solution: objective 165310.00000\n",
      "Presolve removed 87 rows and 395 columns\n",
      "Presolve time: 0.02s\n",
      "Presolved: 123 rows, 244 columns, 944 nonzeros\n",
      "Variable types: 0 continuous, 244 integer (238 binary)\n",
      "\n",
      "Root relaxation: objective 6.992552e+04, 72 iterations, 0.00 seconds (0.00 work units)\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0 69925.5200    0   10 165310.000 69925.5200  57.7%     -    0s\n",
      "H    0     0                    73505.000000 69925.5200  4.87%     -    0s\n",
      "H    0     0                    72956.000000 69925.5200  4.15%     -    0s\n",
      "     0     0 70597.2553    0   26 72956.0000 70597.2553  3.23%     -    0s\n",
      "     0     0 70597.2553    0    8 72956.0000 70597.2553  3.23%     -    0s\n",
      "H    0     0                    70821.000000 70597.2553  0.32%     -    0s\n",
      "     0     0 70621.7333    0   14 70821.0000 70621.7333  0.28%     -    0s\n",
      "     0     0 infeasible    0      70821.0000 70821.0000  0.00%     -    0s\n",
      "\n",
      "Cutting planes:\n",
      "  Gomory: 2\n",
      "  Implied bound: 1\n",
      "  MIR: 1\n",
      "  Mod-K: 2\n",
      "  RLT: 3\n",
      "\n",
      "Explored 1 nodes (251 simplex iterations) in 0.06 seconds (0.02 work units)\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 4: 70821 72956 73505 165310 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 7.082100000000e+04, best bound 7.082100000000e+04, gap 0.0000%\n",
      "\n",
      "Albert assigned to Customer1 (Equipment Setup) in Mannheim. Start at t=24.00.\n",
      "Bob assigned to Customer2 (Equipment Setup) in Karlsruhe. Start at t=50.00.\n",
      "Ed assigned to Customer3 (Repair - Regular) in Baden-Baden. Start at t=67.00.\n",
      "Doris assigned to Customer4 (Equipment Installation) in Buehl. Start at t=120.00.\n",
      "Flor assigned to Customer5 (Equipment Installation) in Offenburg. Start at t=240.00.\n",
      "Doris assigned to Customer6 (Repair - Critical) in Lahr/Schwarzwald. Start at t=300.00.\n",
      "Albert assigned to Customer7 (Inspect/Service Equipment) in Loerrach. Start at t=360.00.\n",
      "\n",
      "Albert's route: Heidelberg -> Mannheim (dist=24.0, t=24.00, proc=30.0, a=0.0, b=30.0) -> Loerrach (dist=160.0, t=360.00, proc=60.0, a=360.0, b=480.0) -> Heidelberg (dist=150.0)\n",
      "Bob's route: Heidelberg -> Karlsruhe (dist=50.0, t=50.00, proc=30.0, a=30.0, b=150.0) -> Heidelberg (dist=50.0)\n",
      "Carlos is not used\n",
      "Doris's route: Freiburg im Breisgau -> Buehl (dist=62.0, t=120.00, proc=60.0, a=120.0, b=240.0) -> Lahr/Schwarzwald (dist=40.0, t=300.00, proc=60.0, a=300.0, b=420.0) -> Freiburg im Breisgau (dist=39.0)\n",
      "Ed's route: Heidelberg -> Baden-Baden (dist=67.0, t=67.00, proc=60.0, a=60.0, b=180.0) -> Heidelberg (dist=67.0)\n",
      "Flor's route: Freiburg im Breisgau -> Offenburg (dist=45.0, t=240.00, proc=60.0, a=240.0, b=360.0) -> Freiburg im Breisgau (dist=45.0)\n",
      "Gina is not used\n",
      "\n",
      "Albert's utilization is 88.33% (424.00/480.00)\n",
      "Bob's utilization is 27.08% (130.00/480.00)\n",
      "Carlos's utilization is 0.00% (0.00/480.00)\n",
      "Doris's utilization is 54.37% (261.00/480.00)\n",
      "Ed's utilization is 40.42% (194.00/480.00)\n",
      "Flor's utilization is 41.67% (150.00/360.00)\n",
      "Gina's utilization is 0.00% (0.00/360.00)\n",
      "Total technician utilization is 37.15% (1159.00/3120.00)\n",
      "Freeing default Gurobi environment\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    # Base model\n",
    "    printScen(\"Solving base scenario model\")\n",
    "    solve_trs0(technicians, customers, dist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scenario Analysis\n",
    "For the base scenario, we have enough technician capacity to satisfy customers demand. Notice that  all jobs were completed and they were completed within time window limits.\n",
    "\n",
    "The first report describes which technician was assigned to each customer, the location of the customer, and the start time of the job. The second report describes the route of each assigned technician. The route defines the *from-location* and the \n",
    "*to-location*. The parameter *dist*  defines the number of minutes that it takes to drive from the *from-location* to the *to-location*. The parameter t determines the *start-time* of the job at the *to-location*. The parameter *proc*  shows the number of minutes that it takes the technician to complete the job. \n",
    "The third report describes the capacity utilization of each technician and the overall capacity utilization of all technicians. The technician capacity utilization is the number of minutes the technician spends driving or serving customers, divided by the technician capacity. The overall capacity utilization of all technicians is the total number of minutes that all technicians spend driving or serving customers, divided by the total capacity of all the technicians available. \n",
    "\n",
    "**Note**:\n",
    "\n",
    "With the current objective function, you can get very different results and all of them are correct. Because the objective function mainly focuses on minimizing unfilled demands. So, you can get a solution with 4 routes and another one with 6."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "In this Jupyter Notebook, we formulated and solved a multi-depot vehicle routing problem with time window constraints using the Gurobi Python API. This MIP formulation is an optimization application for the telecommunication industry; however, the formulation is quite general and can easily be adapted to any kind of vehicle routing problems in the transportation and logistics industries.\n",
    "\n",
    "The routing and scheduling problem that we tackled considers a telecom firm that operates multiple service centers to serve its customers. We solved this routing and scheduling problem by simultaneously making three types of decisions: \n",
    "- (i) the assignment of jobs to a technician at all the service centers\n",
    "- (ii) the routing of each technician, i.e. the sequence/order of customers for a technician to visit\n",
    "- (iii) the scheduling of jobs, i.e. the earliest and latest arrival times for a technician to arrive at a customer location and complete the corresponding job. \n",
    "\n",
    "The objective of the telecom firm is to maximize the total number of completed jobs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "[1] S. Salhi, A. Imran, N. A. Wassan. *The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation*. Computers & Operations Research 52 (2014) 315-325."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copyright © 2023 Gurobi Optimization, LLC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.18"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
